package day0411;

import java.util.Arrays;

public class Test03 {

    public static void main(String[] args) {
        int[] arr = {12 , 46 , 39 , 9 , 27 , 18};
        System.out.println("排序前："+Arrays.toString(arr));
        sort(arr, 0, arr.length - 1);
        System.out.println("排序后："+Arrays.toString(arr));
    }

    //排序
    public static void sort(int[] arr , int left , int right){
        if(arr==null || arr.length==0 || arr.length==1){
            return;
        }

        quickSort(arr , left , right);
    }

    //快速排序
    private static void quickSort(int[] arr, int left, int right) {
        //出口
        if(left>=right){
            return;
        }

        //初始值
        int i = left;
        int j = right;
        int temp = arr[left];

        //排序
        while (i<j){
            //从右往左
            while( (i<j) && arr[j]>=temp){
                j--;
            }
            //放置元素
            if(i<j){
                arr[i++] = arr[j];
            }

            //从左往右
            while((i<j) && arr[i]<=temp){
                i++;
            }
            //放置元素
            if(i<j){
                arr[j--] = arr[i];
            }

            //比较一轮
            System.out.println(Arrays.toString(arr));
        }

        //放置temp元素
        arr[i] = temp;
        //递归
        //左边数列都比temp小
        quickSort(arr , left , i-1);
        //右边数列都比temp大
        quickSort(arr , i+1 , right);
    }

}
